coins = [2, 4, 5]
amount = 11
#我们对其中每一种硬币都可以选择不取用，取用1，2，3....
def coinChange(coins,amount):
    #创建状态转移方程
    dp=[[-1 for _ in range(amount+1)] for _ in range(len(coins))]
    #处理第一行
    for i in range(amount+1):
        if int(i)%int(coins[0])==0:
            dp[0][i]=int(i/coins[0])
    for i in range(1,len(coins)):
        for j in range(amount+1):
                #dp[i-1][j]!=-1
                #先赋值为其上方的元素
            dp[i][j]=dp[i-1][j]
            if j>=coins[i] and dp[i][j-coins[i]]!=-1:
                #容量足以包含当前的数值时,且前面的数值不是-1
                if dp[i][j]==-1:
                        dp[i][j]=dp[i][j-coins[i]]+1
                else:
                    dp[i][j]=min(dp[i][j],dp[i][j-coins[i]]+1)
    print(dp)
coinChange(coins,amount)